package com.leetcode.partition1;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2022/1/8 8:45
 */
public class LC89格雷编码 {

    private static int N = 0;
    private static boolean[] visited;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        List<Integer> answer = grayCode(n);
        for (Integer ans : answer) writer.write(ans + " ");
        writer.flush();
    }

    public static List<Integer> grayCode(int n) {
        List<Integer> answer = new ArrayList<>();
        N = n;
        visited = new boolean[1 << n];
        visited[0] = true;
        dfs(0, answer);
        return answer;
    }

    private static boolean dfs(int u, List<Integer> path) {
        if (path.size() == 1 << N) return true;
        path.add(u);
        visited[u] = true;
        for (int i = 0; i < N; i++) {
            //改变u的每一位得到下一个值
            int v = u ^ (1 << i);
            if (!visited[v] && dfs(v, path)) return true;
        }
        visited[u] = false;
        return false;
    }
}
